package com.leetcode.q23;

/**
 * <p> description: 合并k个有序链表，简单暴力就是每次合并前2个
 * 这个很明显可以用分治法，不过在分解list的过程中感觉反而会消耗较多时间
 * </p>
 *
 * @author tanzc
 * @date 2022/3/31
 **/
public class MergeKLists {
    public ListNode mergeKListsBak(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        ListNode list = lists[0];
        for (int i = 1; i < lists.length; i++) {
            ListNode list2 = lists[i];
            list = mergeTwoLists(list, list2);
        }
        return list;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        if (lists.length == 2) {
            return mergeTwoLists(lists[0], lists[1]);
        }
        int mid = lists.length / 2;
        ListNode[] list1 = new ListNode[mid];
        for (int i = 0; i < mid; i++) {
            list1[i] = lists[i];
        }
        ListNode[] list2 = new ListNode[lists.length - mid];
        for (int j = mid; j < lists.length; j++) {
            list2[j - mid] = lists[j];
        }
        return mergeTwoLists(mergeKLists(list1), mergeKLists(list2));
    }

    // 这个直接从q21 copy过来的，这个的写法也可以优化
    public ListNode mergeTwoListsBak(ListNode list1, ListNode list2) {
        ListNode list = new ListNode();
        ListNode q = list;
        ListNode l1 = list1, l2 = list2;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                q.next = list1;
                q = q.next;
                list1 = list1.next;
            } else {
                q.next = list2;
                q = q.next;
                list2 = list2.next;
            }
        }
        if (list1 == null) {
            q.next = list2;
        } else {
            q.next = list1;
        }

        return list.next;
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        ListNode list;
        if (list1.val <= list2.val) {
            list = list1;
            list.next = mergeTwoLists(list1.next, list2);
        } else {
            list = list2;
            list.next = mergeTwoLists(list1, list2.next);
        }
        return list;
    }

}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}